package code1_100.code11_20;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//电话号码的字母组合:回溯法深度优先便利
public class Code17 {

    public class Solution {

        public List<String> letterCombinations(String digits) {
            List<String> str = new ArrayList<>();
            if (digits.length()==0)
                return str;

            Map<Character, String> phoneMap = new HashMap<Character, String>() {{
                put('2', "abc");
                put('3', "def");
                put('4', "ghi");
                put('5', "jkl");
                put('6', "mno");
                put('7', "pqrs");
                put('8', "tuv");
                put('9', "wxyz");
            }};

            backtrack(str, phoneMap, digits, 0, new StringBuffer());
            return str;
        }

        public void backtrack(List<String> strs, Map<Character, String> map, String digits, int index, StringBuffer str) {
            if (index==digits.length())
                strs.add(str.toString());
            else {
                char ch = digits.charAt(index);
                String s = map.get(ch);
                for (int i=0;i<s.length();i++){
                    str.append(s.charAt(i));
                    backtrack(strs,map,digits,index+1,str);
                    str.deleteCharAt(index);
                }
            }
        }

    }


}

